Queries are very widely used for information retrieval within computing systems. An important class of query is approximate query, in which the documents are characterized by a feature vector in a high dimension space. A query may specify another feature vector based on another document, and the goal may be to search for documents that are within a certain distance of the presented feature vector, or to find a set of documents that are the nearest to the presented feature vector. In most cases of approximate query, a computing system includes a very large number of documents. Therefore, finding a number of documents that are nearest to, or most closely match, the approximate query may be prohibitively expensive.